Algorithme PageRank - Corrigé

Le PageRank (PR) est un algorithme d'analyse des liens utilisé par le moteur de recherche Google pour classer des pages web. Il permet de mesurer avec un indicateur numérique la popularité d'une page web.
Le PageRank est donc l'un des indicateurs qui permettent de classer les pages du Web dans les résultats de recherche de Google (il mesure la popularité mais pas nécessairement la pertinence de la page web).
Ce système a été inventé par Larry Page, cofondateur de Google.

L'objectif de cet exercice est de comprendre le fonctionnement du PR à petite échelle.

Imaginons le réseau de 5 pages ci-dessous. Les flèches représentent les liens qui pointent vers une autre page (par exemple, la flèche de 1 vers 5 signifie qu'il existe sur la page 1 un lien vers la page 5).

Admettons qu'un internaute qui vient de consulter une page donnée à une probabilité  `p\in]0;1[` de rester sur cette page ou de choisir une autre page non liée (avec équiprobabilité entre toutes les pages) et une probabilité  \(1-p\)  de cliquer sur l'un des liens de cette page (avec équiprobabilité entre tous les liens).

Ainsi, par exemple, à partir de la page 1, il peut rester sur la page 1 ou aller vers la page 4 (probabilité de  \(\dfrac{p}{2}\)  pour chaque) ou cliquer sur trois liens, vers les pages 2, 3 et 5 (probabilités de  \(\dfrac{1-p}{3}\)  pour chaque).

En imaginant que l'internaute surfe sur Internet sans mémoire des états précédents, ce processus est une chaîne de Markov.

1. Écrire sa matrice de transition dans le cas de l'exemple avec `p=0,7` .

2. Justifier que cette chaîne de Markov admet une unique distribution invariante et la déterminer dans le cas de l'exemple.

3. Comment peut-on utiliser cette modélisation pour classer les pages par popularité décroissante ? 

Solution

1. La matrice de transition de cette chaîne de Markov est :
\(T=\begin{pmatrix} 0,35&0,1&0,1&0,35&0,1\\0,1&0,35&0,35&0,1&0,1\\0,175&0,175&0,175&0,3&0,175\\0,175&0,175&0,3&0,175&0,175\\0,175&0,175&0,175&0,3&0,175 \end{pmatrix}\)

2. Cette matrice ne comporte pas de  \(0\)  donc, d'après le cours, il existe une unique distribution invariante  \(X=\begin{pmatrix} v&w&x&y&z\end{pmatrix}\) .
On a  \(\begin{cases}X=XT\\v+w+x+y+z=1\end{cases}\)
\(\Leftrightarrow\begin{cases}0,35v+0,1w+0,175x+0,175y+0,175z=v\\0,1v+0,35w+0,175x+0,175y+0,175z=w\\0,1v+0,35w+0,175x+0,3y+0,175z=x\\0,35v+0,1w+0,3x+0,175y+0,3z=y\\0,1v+0,1w+0,175x+0,175y+0,175z=z \\v+w+x+y+z=1\end{cases}\)
On peut remplacer la première équation par la première moins la deuxième, la deuxième par la deuxième moins la cinquième, la troisième par la troisième moins la cinquième, la quatrième par la quatrième moins la première et on peut supprimer une équation, par exemple la cinquième.
Ce qui donne :  \(\begin{cases}v=w\\ z=0,75w\\8x- y=8w\\8y-x=8,75w\\2,75w+x+y=1\\\end{cases}\)
En résolvant ce système, par exemple à la calculatrice, on obtient \(X=\begin {pmatrix} 0,2083 &0,2083 &0,1563&0,1771 &0,25 \end{pmatrix}\) .

3. D'après le cours, la chaîne de Markov ayant un nombre d'états fini tend vers sa distribution invariante donc par ordre de popularité, on va trouver les pages 5, puis 1 et 2, puis 4, puis 3.